#include <bits/stdc++.h> // 包含所有标准库头文件，方便编程
using namespace std;     // 使用标准命名空间，避免每次写std::

const int MOD = 998244353, seed = 233;
// MOD: 哈希取模的大质数(防止溢出)
// seed: 哈希种子(类似进制数)
const int N = 100005; // 定义最大字符串长度

string s;  // 存储待处理的字符串
int h[N];  // h[i]: 存储字符串前i+1个字符的哈希值
int qp[N]; // qp[i]: 存储seed的i次方 % MOD的值(预计算幂次)

// 初始化哈希值
void init_hash(string s)
{
  qp[0] = 1;         // seed的0次方=1
  h[0] = s[0] % MOD; // 第一个字符的哈希就是它自己 % MOD

  for (int i = 1; i < s.size(); ++i)
  { // 从第二个字符开始计算
    // 当前哈希 = 前一个哈希*seed + 当前字符，再取模
    h[i] = (1ll * h[i - 1] * seed % MOD + s[i]) % MOD; // 1ll: 转为long long防溢出
    // 计算seed的i次方 % MOD
    qp[i] = 1ll * qp[i - 1] * seed % MOD; // 用前一次结果*seed再取模
  }
}
// 获取子串s[l..r]的哈希值
int get_hash(int l, int r)
{
  if (l == 0)    // 如果是整个字符串的前缀
    return h[r]; // 直接返回预存的哈希值
  // 公式：hash = (h[r] - h[l-1]*seed^(r-l+1)) % MOD
  // 加MOD是为了防止负数，最后再取模
  return (h[r] + MOD - 1ll * h[l - 1] * qp[r - l + 1] % MOD) % MOD;
}